package P147_对链表进行插入排序;
//链表插入排序

  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      public void pp(){
          ListNode x = this;
          while(x != null){
              System.out.println(x.val);
              x = x.next;
          }
      }

      @Override
      public String toString() {
          String x = "";
          ListNode b = this;
          while(b != null){
              x+=b.val+"->";
              b=b.next;
          }
          return x.substring(0,x.length()-2);
      }
  }

public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null){
            return head;
        }
        //链表相关的，要注意头部前面再添加一个占位头（防止链表头可能被换）
        ListNode sHead = new ListNode(-1);
        ListNode pre,cur;
        sHead.next = head;
        while(head != null && head.next != null){
            if(head.val < head.next.val){
                head = head.next;
                continue;
            }
            pre = sHead;
            //每次都从哑头开始，判断next的val和当前需要判断的head.next的val的大小
            while(pre.next.val < head.next.val){
                pre = pre.next;
            }
            //head的下一个节点插到pre.next中即可
            cur = head.next;
            head.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
        }
        return sHead.next;
    }

    public static void main(String args[]){
        int[] arr = {2,1,3};
        ListNode head = new ListNode(4);
        ListNode p = head;
        for(int i= 0;i<arr.length;i++){
            ListNode tmpNode = new ListNode(arr[i]);
            head.next = tmpNode;
            head = head.next;
        }
        p.pp();
        ListNode x= new Solution().sortList(p);
        System.out.println(x);
    }
}
